package com.example.leetdemo.process;

import java.util.*;

public class Solution851 {


    /**
     * 超时
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < richer.length; i++) {
            if (map.containsKey(richer[i][1])) {
                Set<Integer> p = map.get(richer[i][1]);
                p.add(richer[i][0]);
                map.put(richer[i][1], p);
            } else {
                Set<Integer> p = new HashSet<>();
                p.add(richer[i][0]);
                map.put(richer[i][1], p);
            }
        }
        List<Set<Integer>> list = new ArrayList<>();
        for (int i = 0; i < quiet.length; i++) {
            if (map.containsKey(i)) {
                Set<Integer> set = map.get(i);
                Set<Integer> temp = new HashSet<>(set);
                temp.add(i);
                while (true) {
                    Set<Integer> newSet = new HashSet<>();
                    for (Integer number: set) {
                        if (map.containsKey(number)) {
                            temp.addAll(map.get(number));
                            newSet.addAll(map.get(number));
                        }
                    }
                    if (newSet.size() > 0) {
                        set = newSet;
                    } else {
                        break;
                    }
                }
                list.add(temp);
            } else {
                Set<Integer> temp = new HashSet<>();
                temp.add(i);
                list.add(temp);
            }
        }
        int[] result = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            int min = quiet.length + 1;
            for (Integer que : list.get(i)) {
                if (min > quiet[que]) {
                    result[i] = que;
                    min = quiet[que];
                }
            }
        }
        return result;
    }
    /**
     *                   {4,5,6}, 3, {{1, 0}, 7}
     *                   2,1,0
     *
     */

    /**
     * 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
     * 输出：[5,5,2,5,4,5,6,7]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/loud-and-rich
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public int[] loudAndRich2(int[][] richer, int[] quiet) {
        int[] result = new int[quiet.length];
        List<List<Integer>> l = new ArrayList<>();

        return result;
    }

}
